\documentclass{article}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage[usenames,dvipsnames]{color} % For colors and names
\usepackage{hyperref}
\usepackage{tabularx}
\usepackage{pgfplots}
\hyphenpenalty=1115000

\title{\textbf{Metody Odkrywania Wiedzy 12L} \\ Temat analityczny: Detekcja wczesnych stadiów raka piersi \\ Dokumentacja projektu} % Title

\author{Tomasz \textsc{Bawej} \\ Łukasz \textsc{Trzaska}} % Author name

\definecolor{mygrey}{gray}{.96} % Light Grey
\lstset{language=Verilog, tabsize=3, backgroundcolor=\color{mygrey}, basicstyle=\small, commentstyle=\color{BrickRed}}
\lstset{ 
	language=[ISO]C++,              % choose the language of the code ("language=Verilog" is popular as well)
   tabsize=3,							  % sets the size of the tabs in spaces (1 Tab is replaced with 3 spaces)
	basicstyle=\scriptsize,               % the size of the fonts that are used for the code
	numbers=left,                   % where to put the line-numbers
	numberstyle=\scriptsize,              % the size of the fonts that are used for the line-numbers
	stepnumber=2,                   % the step between two line-numbers. If it's 1 each line will be numbered
	numbersep=5pt,                  % how far the line-numbers are from the code
	backgroundcolor=\color{mygrey}, % choose the background color. You must add \usepackage{color}
	%showspaces=false,              % show spaces adding particular underscores
	%showstringspaces=false,        % underline spaces within strings
	%showtabs=false,                % show tabs within strings adding particular underscores
	frame=single,	                 % adds a frame around the code
	tabsize=3,	                    % sets default tabsize to 2 spaces
	captionpos=b,                   % sets the caption-position to bottom
	breaklines=true,                % sets automatic line breaking
	breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
	%escapeinside={\%*}{*)},        % if you want to add a comment within your code
	commentstyle=\color{BrickRed}   % sets the comment style
}

\begin{document}

\maketitle % Insert the title, author and date

\setlength\parindent{0pt} % Removes all indentation from paragraphs

% \renewcommand{\labelenumi}{\alph{enumi}.} 
\newenvironment{packed_enum}{
\begin{enumerate}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{enumerate}}

\section{Opis zadania}
Niniejszy dokument dotyczy analitycznego zadania klasyfikacji przeprowadzonej dla danych umieszczonych na stronie \url{http://www.sigkdd.org/kddcup/index.php?section=2008&method=info}
Zgodnie z wymaganiami zamieszczonymi na stronie przedmiotu, zakres projektu winien obejmować następujące czynności:
\begin{itemize}
\item przygotowanie danych,
\item statystyczny opis danych,
\item transformację danych (np. dyskretyzację, kodowanie atrybutów dyskretnych, standaryzację),
\item selekcja atrybutów,
\item strojenie parametrów algorytmów,
\item tworzenie modeli,
\item wnikliwa ocena jakości modeli,
\end{itemize}

Ponadto klasyfikacyjna natura zadania pociąga za sobą konieczność przeprowadzenia następujących czynności:

\begin{itemize}
\item ustalenia atrybutu dyskretnego reprezentującego pojęcie docelowe,
\item określenia zakresu przygotowania danych (np. przetworzenia do odpowiedniej postaci tabelarycznej, modyfikacji typów/zbiorów wartości atrybutów, eliminacji/naprawy defektów danych, modyfikacji rozkładu kategorii, losowania podzbiorów danych),
\item określenia zakresu i technik statystycznego opisu danych (np. charakterystyki rozkładu wartości atrybytów, detekcji wartości odstających, detekcji zależności między atrybutami),
\item wskazania możliwości zdefiniowania nowych atrybutów,
\item ustalenia kryteriów lub algorytmu selekcji atrybutów,
\item wyboru algorytmów klasyfikacji,
\item wskazania parametrów algorytmów klasyfikacji wymagających strojenia,
\item ustalenia procedur i kryteriów oceny jakości modeli (z uwzględnieniem rozkładu oraz, tam gdzie to uzasadnione, kosztów pomyłek). 
\end{itemize} 

Opis danych treningowych oraz czynności wynikających bezpośrednio z ich charakteru stanowi temat odrędbnego rozdziału: \ref{sec:data}.
\section{Cel klasyfikacji}
\begin{itemize}
\item Przyporządkować próbkę powstałą ze zdjęcia piersi do jednej z klas: zmiana łagodna (\textit{ang. benign}) / zmiana złośliwa (\textit{ang. malignant}).
\item Trenując klasyfikatory szczególną uwagę zwrócić na minimalizację błędu drugiego rodzaju (ang. \textit{false negative}), aby przypadki złośliwe nie uległy przeoczeniu.
\end{itemize}

\section{Opis dostępnych danych}
\label{sec:data}

Analizowane w ramach projektu dane pochodzą z konkursu \textit{KDD Cup 2008}, którego problematyka dotyczyła wczesnej detekcji raka piersi. Same dane reprezentują zbiór przetworzonych obszarów zdjęć rentgenowskich wykonanych dla grupy 118 chorych i 1594 zdrowych pacjentów. Zbór treningowy zawiera łącznie 102294 próbki (określane też zamiennie mianem obszarów lub kandydatów), z których jedynie niewielka część przedstawia zmiany złośliwe. Pewne uproszczenie zadania stanowi fakt, iż zgromadzone  dane ograniczają się do przypadków, w których na jednego pacjenta przypada nie więcej niż jedna zmiana nowotworowa.
\\
Dane podzielone zostały na zbiór cech oraz informacji o każdej próbce. Zestaw cech liczy 117 atrybutów będących liczbowymi wynikami działania pewnych algorytmów przetwarzania obrazów. Informacja o próbce zawiera 11 atrybutów, które opisane została w Tabeli 1.

\begin{table}[h]\footnotesize
\caption{Atrybuty opsujące próbkę}
\begin{tabularx}{\textwidth}{ |X|X| }
  \hline
  \textbf{Atrybut} & \textbf{Opis} \\
  \hline
  \textit{Ground truth label}  & 1 dla zmian złośliwych, -1 dla łagodnych.\\
  \textit{Image-Finding-ID} & Unikalny identyfikator zmiany złośliwej, 0 dla zmian łagodnych. Wartość pozwala rozpoznać tę samą zmianę widoczną na różnych zdjęciach tego samego typu.\\
  \textit{Study-Finding-ID} & Unikalny identyfikator zmiany pozwalający rozpoznać tę samą zmianę na różnych zdjęciach, bez względu na typ zdjęcia i złośliwość samej zmiany.\\
  \hline  
  \textit{Image-ID} & Unikalny identifikator obrazu na podstawie którego wygenerowano próbkę.\\
  \textit{Study-ID} & Unikalny identyfikator pacjenta. Dla każdego pacjenta przechowywane są 4 zdjęcia, na ogół ze wszystkich 4. generowane są próbki.\\
  \textit{LeftBreast} & 1 jeśli obraz lewej piersi, 0 w przeciwnym przypadku.\\
  \textit{MLO} & 1 jeśli obraz MLO, 0 w przeciwnym przypadku. \\
  \textit{Candidate-X} & Współrzędna X zmiany.\\
  \textit{Candidate-Y} & Współrzędna Y zmiany.\\
  \textit{Nipple-X} & Współrzędna X sutka.\\  
  \textit{Nipple-Y} & Współrzędna Y sutka.\\
  \hline
\end{tabularx}
\end{table}
\pagebreak
\paragraph*{Dane użyteczne.}
Udostępnione przez organizatorów konkursu dane podzielone zostały na zbiory: testowy oraz treningowy, przy czym ze względu na formułę konkursu zbiór testowy został pozbawiony pierwszych 3 elementów opisu (klasa próbki oraz identyfikatory zmiany). Tym samym zbiór danych użytecznych z punktu widzenia zadania ogranicza się do dostępnego zbioru treningowego. Wartość pierwszej kolumny ze zbioru informacji stanowi jednocześnie wartość pojęcia docelowego (atrybut \textit{Ground truth label}), podczas gdy kolumny \textit{MLO}, \textit{Candidate-X}, \textit{Candidate-Y}, \textit{Nipple-X}, \textit{Nipple-Y} prawdopodobnie nie mają wartości informacyjnej.
\begin{table}[h]\footnotesize
\caption{Statystyki danych dla pojedynczego pacjenta}
\begin{tabularx}{\textwidth}{ |X|X|X|X|X|X|X|X| }
  \cline{1-8}
	\textit{Image-ID} & \textit{Patient-ID} & \textit{LBreast} & \textit{MLO} &
	\textit{Cand-X} & \textit{Cand-Y} & \textit{Nipple-X} & \textit{Nipple-Y} \\ 
  \cline{1-8}
  \multicolumn{8}{|c|}{Liczba unikalnych wartości} \\
  \cline{1-8}
  6848 & 1712 & 2 & 2 & 3273 & 3407 & 1449 & 1172 \\
  \cline{1-8}
  \multicolumn{8}{|c|}{Średnia liczba unikalnych wartości w przeliczeniu na pacjenta} \\
  \cline{1-8}
	4 & 1 & 2 & 2 & 57.44 & 57.34 & 3.99 & 3.99 \\
  \cline{1-8}  
  \multicolumn{8}{|c|}{Minimalna liczba unikalnych wartości w przeliczeniu na pacjenta} \\
  \cline{1-8}  
  4 & 1 & 2 & 2 & 302 & 307 & 4 & 4 \\
  \cline{1-8}  
  \multicolumn{8}{|c|}{Maksymalna liczba unikalnych wartości w przeliczeniu na pacjenta} \\
  \cline{1-8}  
  4  & 1 & 2 & 2 & 6 & 6 & 3 & 3 \\
  \cline{1-8}
\end{tabularx}
\end{table}
\pagebreak
W Tabeli 2. zestawiono statystykę danych, która potwierdza, iż dla każdego pacjenta wykonano 4 zdjęcia.  Następnie na ich podstawie utworzono pewną liczbę próbek (różną dla różnych pacjentów). Dodatkowym mankamentem, lub - operując nomenklaturą konkursową - wyzwaniem, jest także fakt, iż aż 101671 próbek reprezentuje przypadki łagodne (pierwsza klasa pojęcia docelowego), a tylko 623 reprezentuje przypadki złośliwe (druga klasa pojęcia docelowego) tzn. stosunek klas to w przybliżeniu $6/1000$.
\section{Rozwiązanie}
\paragraph*{Opis koncepcyjny.} Nie mogąc weryfikować rozwiązania na pełnoprawnym zbiorze testowym, użyto  walidacji krzyżowej 10 stopniowej, przybliżając tym samym oczekiwaną jakość klasyfikatorów. Użyto klasyfikatora \textit{czułego an koszt pomyłek}, aby spróbować zrównoważyć znaczne dysproporcje liczności klas. Próbki podzielono na 4 grupy ze względu na typ zdjęcia, na których to grupach osobno trenowano klasyfikatory:
\begin{itemize}
\item lewa pierś i zdjęcie CC
\item lewa pierś i zdjęcie MLO
\item prawa pierś i zdjęcie CC
\item prawa pierś i zdjęcie MLO
\end{itemize}

Większość prezentowanych wyników dotyczy zatem czterech osobnych klasyfikatorów. Próba wytrenowania klasyfikatorów dla pełnego zbioru nierozróżnialnych ze względu na typ zdjęcia próbek nie rokowała lepiej pod względem wyników, a ostatecznie skazana została na porażkę ze względu na dużo dłuższy czas trenowania i szacowania jakości. O ile problem ewaluacji jakości można by usiłować łagodzić wprowadzając do zbioru cech atrybuty reprezentujące typ zdjęcia, o tyle problem czasochłonności rozwiązać mogło jedynie przycięcie zbioru treningowego do dwóch równolicznych ze względu na klasę próbki grup. Podejście to obarczone było jednak dużym błędem klasyfikacji dla pełnego zbioru danych (utrata zdolności generalizacji w stosunku do negatywnych próbek).
\paragraph*{Implementacja.}
Model zaimplementowano w języku R z użyciem biblioteki \textit{RWeka}. Procesowi trenowania i oceny jakości dla powyższych 4 typów próbek poddano następujące klasyfikatory:
\begin{itemize}
\item \textbf{SMO}: wektor maszyn podpierających trenowany algorytmem sekwencyjnej minimalizacji John'a C. Platt'a (biblioteka Weka: \textit{weka.classifiers.functions.SMO)}
\item \textbf{Bagging}: klasyfikator agregowany \\ (biblioteka Weka: \textit{weka.classifiers.meta.Bagging)}
\item \textbf{J48}: drzewo decyzyjne C4.5 \\ (biblioteka Weka: \textit{weka.classifiers.trees.J48)}
\item \textbf{SimpleLogistic}: logistyczna regresja liniowa \\ (biblioteka Weka: \textit{weka.classifiers.functions.SimpleLogistic)}
\item \textbf{KNN}: klasyfikator \textit{najbliższych sąsiadów} \\ (biblioteka Weka: \textit{weka.classifiers.functions.IBk)}.
\end{itemize}
Klasyfikator \textit{najbliższych sąsiadów} przetestowano kilkukrotnie i z uwagi na jego niską skuteczność oraz dużą czasochłonność zrezygnowano z prezentacji podsumowania jego osiągów.
\paragraph*{Iteracyjne strojenie algorytmów.}
Korzystając z dekoratora klasyfikatorów uwrażliwiającego je na koszty pomyłek (Weka:  \textit{weka.classifiers.meta.CostSensitiveClassifier}), minimalizowany jest błąd drugiego rodzaju (ang.  \textit{false negative}). W kolejnych iteracjach podawana jest macierz kosztów pomyłek, nakładająca większą karę za pomyłkę przydziału próbki \textit{malignant} do klasy \textit{benign}. Podsumowanie właściwości klasyfikatora strojonego w ten właśnie sposób zaprezentowano na Rysunku \ref{pic:najlep-rezultaty-cc} w rozdziale \ref{sec:wyniki}. Jako przykład obrano klasyfikator \textit{Bagging}, który w ostatniej iteracji uzyskał stosunkowo satysfakcjonujące wyniki.
\paragraph*{Kluczowe pliki} (funkcje i sekwencje czynności) zaimplementowane w R:
\begin{itemize}
\item \textbf{prepData.r} wczytuje plik źródłowy informacyjny \textit{info.txt} i przekształca go na format \textit{.arff}
\item \textbf{readData.r} wczytuje pliki źródłowe z danymi \textit{features.txt} oraz informacyjny \textit{info.txt} i scala je do jednej ramki danych  \textit{dataAll}
\item \textbf{unbindData.r} z zadanej ramki danych eliminuje zadane kolumny
\item \textbf{craftData.r} przycina dane do konkretnej kategorii np. tylko lewa pierś 
\item \textbf{scenarioBody.r} dla zadanej ramki danych \textit{trainData}, która była przygotowana wcześniej dla konkretnego typu danych, wykonuje trening i agreguje wyniki dla poszczególnych klasyfikatorów.\\
Wszystkie pliki źródłowe znajdują się w katalogu projektu \textit{/src}.
\end{itemize}
\paragraph*{Ocena jakości modeli}
Ewaluacji modeli dokonywano za pomocą metody walidacji krzyżowej 10 stopniowej. Do tego celu zastosowano dostępną w bibliotece Weka funkcję: \textit{evaluate\_Weka\_classifier}. W rezultacie jej działania otrzymano następujące wskaźniki: \textit{Quality}, \textit{False positive}, \textit{False}, \textit{True positive}, \textit{True negative}.  
\section{Wyniki}
\label{sec:wyniki}
\paragraph*{Pliki w projekcie.} Wszystkie uzyskane rezultaty odnaleźć można w plikach projektowych w katalogu \textit{results}. Pliki z rozszerzeniem \textit{.txt} zawierają rezultaty czytelne dla człowieka, natomiast pliki z rozszerzeniem \textit{.table} czytelne dla funkcji \textit{read.table} środowiska R.\\
Jak zaprezentowano na Rysunku \ref{fig:postep-klasyf-bagging} postęp w strojeniu klasyfikatora Bagging pod kątem minimalizacji błędu drugiego rodzaju \textit{false-negative} towarzyszył spadkowi jakości klasyfikacji i wzrostowi błędu \textit{false-negative}, ale również poprawie wskaźnika \textit{true-positive}.

\begin{center}
\begin{figure}[h]
\pgfplotsset{width=12cm, compat=1.4}
\begin{tikzpicture}
\begin{axis}[
ybar,
enlargelimits=0.4,
legend style={at={(0.5,-0.25)},
anchor=north,legend columns=-1},
ylabel={wskaźniki},
symbolic x coords={SMO, Bagging, J48, Logistic},
xtick=data,
nodes near coords,
nodes near coords align={vertical}
]
\addplot coordinates {(SMO,0.603) (Bagging,0.952) (J48,0.930) (Logistic,0.947) };
\addplot coordinates {(SMO,0.038) (Bagging,0.31) (J48,0.438) (Logistic,0.289) };
\legend{accuracy, false-negative}
\end{axis}
\end{tikzpicture}
\caption{Najlepsze rezultaty osiągnięte dla próbek typu CC piersi lewej}
\label{pic:najlep-rezultaty-cc}
\end{figure}
\end{center}
Jak zaprezentowano na Rysunku \ref{fig:postep-klasyf-bagging} postęp w strojeniu klasyfikatora Bagging pod kątem minimalizacji błędu drugiego rodzaju \textit{false-negative} towarzyszył spadkowi jakości klasyfikacji i wzrostowi błędu \textit{false-negative}, ale również poprawie wskaźnika \textit{true-positive}.
\begin{center}
\begin{figure}[h]
\pgfplotsset{width=12cm, compat=1.4}
\begin{tikzpicture}
\begin{axis} [
ylabel={wskaźniki},
xlabel={koszt pomy\l{}ki},
]
\addplot+[color=yellow,mark=*]
coordinates
{(1, 0.99) (4, 0.995) (16, 0.995)
(64, 0.994) (256, 0.994) (1024, 0.986) (4096, 0.951)
};
\addlegendentry{accuracy}
\addplot+[color=green,mark=+]
coordinates{
(1, 0.81) (4, 0.66) (16, 0.62)
(64, 0.60) (256, 0.59) (1024, 0.49) (4096, 0.314)
};
\addlegendentry{false-negative rate}
\addplot+[color=red,mark=+]
coordinates{
(1, 0.37) (4, 0.0) (16, 0.0) (64, 0.0) 
(256, 0.002) (1024, 0.01) (4096, 0.004)
};
\addlegendentry{false-positive rate}
\addplot+[blue,mark=*]
coordinates{
(1, 0.18) (4, 0.33) (16, 0.37) (64, 0.40) 
(256, 0.40) (1024, 0.50) (4096, 0.65)
};
\addlegendentry{true-positive rate}
\end{axis}
\end{tikzpicture}
\caption{Postęp w strojeniu klasyfikatora Bagging pod kątem minimalizacji błędu drugiego rodzaju 
\label{fig:postep-klasyf-bagging}
\textit{false-negative}}
\end{figure}
\end{center}
\section{Podsumowanie}
Tak uzyskane wyniki, jak i przebieg działań projektowych ciężko określić mianem sukcsesu, głównie ze względu na brak możliwośći jednoznacznej weryfikacji wyników naszych starań. O ile z konkursowego punktu widzenia operownie na zdegenrowanych danych (brak danych testowych, ogromna dysporoporcja klas) może się wydawać ciekawe, o tyle w przypadku analitycznego projektu staje się niemal pozbawione sensu, gdyż wszelkie wyniki przeprowadzonych analiz są co najwyżej estymacjami jakości klasyfikatorów. Pomimo wytworzenia odpowiedniego kodu, nie zdecydowalifśmy się jednak na podział dostępnych danych na zbior treningowy i testowy, ze względu na brak możliwości uzyskania reprezentatywnego zbioru testowego bez dalszej degenracji danych treningowych.
Po stronie pozytywów zapisać należy jednak zapoznanie się ze środowiskiem R, częścią pakietu RWeka i biblioteki Weka. Niedociągnięcia można by wyliczać dużo dłużej, jednak wielowymiarowość problemu (wybór typu klasyfikatora, parametrów tegoż, podzbiorów danych i atrybutów) uniemożliwiła równomierną analizę każdego możliwego podejścia w sensownych ramach czasowych.

\end{document}
